package xyf.p02.stack_queue;

import java.util.Stack;

/**
 * ClassName: P0084_LargestRectangleArea
 * Description:
 * Author: xyf
 * Date: 9/7/22 7:48 PM
 * Version: 1.0
 **/
public class P0084_LargestRectangleArea
{
    public int largestRectangleArea(int[] heights)
    {
        int[] left = new int[heights.length];

        int[] right = new int[heights.length];

        Stack<Integer> stack = new Stack<>();

        for (int i = heights.length - 1; i >= 0; i--)
        {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i])
            {
                Integer index = stack.pop();
                left[index] = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty())
        {
            Integer index = stack.pop();
            left[index] = -1;
        }

        stack.clear();
        for (int i = 0; i < heights.length; i++)
        {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i])
            {
                Integer index = stack.pop();
                right[index] = i;
            }

            stack.push(i);
        }

        while (!stack.isEmpty())
        {
            Integer index = stack.pop();
            right[index] = heights.length;
        }

        int max = 0;
        for (int i = 0; i < heights.length; i++)
        {
            int cur = (right[i] - left[i] - 1) * heights[i];
            max = Math.max(max, cur);
        }
        return max;
    }
}